import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class LeetCode350 {

    public static void main(String[] args) {
        int[] nums1 = {1, 2};
        int[] nums2 = {1, 1};

        Arrays.stream(intersect(nums1, nums2)).forEach(System.out::println);
    }

    public static int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int[] res = new int[Math.min(nums1.length, nums2.length)];
        int index = 0, index1 = 0, index2 = 0;
        while (index1 < nums1.length && index2 < nums2.length) {
            if (nums1[index1] < nums2[index2]) {
                index1++;
                continue;
            }
            if (nums1[index1] > nums2[index2]) {
                index2++;
                continue;
            }
            if (nums1[index1] == nums2[index2]) {
                res[index++] = nums1[index1];
                index1++;
                index2++;
            }
        }
        return Arrays.copyOfRange(res, 0, index);
    }

    public static int[] intersectHash(int[] nums1, int[] nums2) {
        if (nums1.length < nums2.length) {
            return intersect(nums2, nums1);
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums1) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        int[] res = new int[nums2.length];
        int index = 0;
        for (int num : nums2) {
            if (map.getOrDefault(num, 0) > 0) {
                map.put(num, map.get(num) - 1);
                res[index++] = num;
            }
        }
        return Arrays.copyOfRange(res, 0, index);
    }
}
